Grokking Microsoft Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Microsoft Easy Problems
Buddy Strings (easy)
Solution: Buddy Strings
Can Place Flowers (easy)
Solution: Can Place Flowers
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Maximum Number of Balloons (easy)
Solution: Maximum Number of Balloons
Binary Tree Path Sum (easy)
Solution: Binary Tree Path Sum
Pair with Target Sum (easy)
Solution: Pair with Target Sum
Buy Two Chocolates (easy)
Solution: Buy Two Chocolates
Root Equals Sum of Children (easy)
Solution: Root Equals Sum of Children
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Min Cost Climbing Stairs (easy)
Solution: Min Cost Climbing Stairs
Plus One (easy)
Solution: Plus One
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Find the Index of the First Occurrence in a String (easy)
Solution: Find the Index of the First Occurrence in a String
Merge Two Sorted Lists (easy)
Solution: Merge Two Sorted Lists
Microsoft Medium Problems
Nth Digit (medium)
Solution: Nth Digit
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Find Original Array From Doubled Array (medium)
Solution: Find Original Array From Doubled Array
Reverse Words in a String II (medium)
Solution: Reverse Words in a String II
Longest Arithmetic Subsequence (medium)
Solution: Longest Arithmetic Subsequence
Matchsticks to Square (medium)
Solution: Matchsticks to Square
Score of Parentheses (medium)
Solution: Score of Parentheses
Maximum Length of a Concatenated String with Unique Characters (medium)
Solution: Maximum Length of a Concatenated String with Unique Characters
Inorder Successor in BST (medium)
Solution: Inorder Successor in BST
Distribute Coins in Binary Tree (medium)
Solution: Distribute Coins in Binary Tree
Spiral Matrix (medium)
Solution: Spiral Matrix
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Sum of Subarray Minimums (medium)
Solution: Sum of Subarray Minimums
Rotate Image (medium)
Solution: Rotate Image
Combinations (medium)
Solution: Combinations
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Multiply Strings (medium)
Solution: Multiply Strings
Best Time to Buy and Sell Stock II (medium)
Solution: Best Time to Buy and Sell Stock II
Largest Palindromic Number (medium)
Solution: Largest Palindromic Number
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Next Permutation (medium)
Solution: Next Permutation
132 Pattern (medium)
Solution: 132 Pattern
Valid Sudoku (medium)
Solution: Valid Sudoku
Number of Islands (medium)
Solution: Number of Islands
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Regular Expression Matching (hard)
Solution: Regular Expression Matching
First Missing Positive (hard)
Solution: First Missing Positive
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Sliding Window Maximum (hard)
Solution: Sliding Window Maximum
Count Unique Characters of All Substrings of a Given String (hard)
Solution: Count Unique Characters of All Substrings of a Given String
Word Ladder (hard)
Solution: Word Ladder
Word Ladder II (hard)
Solution: Word Ladder II
Number of Flowers in Full Bloom (hard)
Solution: Number of Flowers in Full Bloom
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Solution: 132 Pattern

Problem Statement

Given an array nums, containing N integers.

A 132 pattern consists of three numbers, say x, y, and z, where x < z and z < y. This is often referred to as a '132' pattern because if we represent x, y, and z as 1, 3, and 2, respectively, it mimics the positional pattern in '132'.

Return true if such a pattern exists within any sequence of given numbers nums. Otherwise, return false.

Examples

  1. Example 1:

    • Input: nums = [3, 5, 0, 3, 4]
    • Expected Output: True
    • Justification: Here, 3 < 4 and 4 < 5, forming a '132' pattern with the numbers 3, 5, and 4.
  2. Example 2:

    • Input: nums = [1, 2, 3, 4]
    • Expected Output: False
    • Justification: The sequence is in ascending order, and no '132' pattern is present.
  3. Example 3:

    • Input: nums = [9, 11, 8, 9, 10, 7, 9]
    • Expected Output: True
    • Justification: The pattern is formed with 8 < 9 and 9 < 10 in sequence 8, 10, 9.

Constraints:

  • n == nums.length
  • 1 <= n <= 2 * 105
  • -109 <= nums[i] <= 109

Solution

The 132 Pattern problem requires finding a sequence of three numbers in an array such that the first number is smaller than the third number, which is in turn smaller than the second number. In other words, for indices i, j, and k, we need to find a pattern where nums[i] < nums[k] < nums[j] with i < j < k.

To solve this problem efficiently, we use a combination of a stack and a set to track potential candidates for the 132 pattern as we iterate through the array from the end to the beginning. This approach ensures that we can quickly identify and verify the necessary conditions for the pattern.

Step-by-Step Algorithm

  1. Initialize Data Structures:

    • Create a SortedSet named second to store potential candidates for the second number in the 132 pattern.
    • Create a stack named st to manage the numbers during the traversal.
  2. Iterate Through the Array from End to Beginning:

    • Loop through the array from the last element to the first element (i.e., from right to left).
  3. Manage the Stack:

    • For each element nums[i] in the array:
      • While the stack is not empty and the top element of the stack is smaller than nums[i], pop the element from the stack and add it to the second set.
  4. Check for the 132 Pattern:

    • If the stack is not empty and the second set is not empty:
      • Iterate through the second set to find the smallest number that is greater than nums[i]. This is done using the higher method of SortedSet which finds the smallest number in the set that is greater than nums[i].
      • If such a number is found, it confirms the presence of the 132 pattern, and we return True.
  5. Push the Current Number onto the Stack:

    • Push the current number nums[i] onto the stack to potentially serve as the second number in future iterations.
  6. End of Iteration:

    • If the loop completes without finding a 132 pattern, return False.

Algorithm Walkthrough

Using the input nums = [9, 11, 8, 9, 10, 7, 9]:

  1. Initialize Data Structures:

    • second = {} (empty set)
    • st = [] (empty stack)
  2. Iteration from End to Beginning:

    • i = 6 (nums[i] = 9):

      • Stack is empty.
      • Push 9 onto the stack: st = [9].
    • i = 5 (nums[i] = 7):

      • Stack contains 9, which is greater than 7.
      • Push 7 onto the stack: st = [9, 7].
    • i = 4 (nums[i] = 10):

      • Pop elements from the stack while they are smaller than 10:
        • Pop 7, insert into second: second = {7}, st = [9].
        • Pop 9, insert into second: second = {7, 9}, st = [].
      • Stack is empty.
      • Push 10 onto the stack: st = [10].
    • i = 3 (nums[i] = 9):

      • Stack contains 10, which is greater than 9.
      • Check second for an element greater than 9:
        • second.upper_bound(9) finds 9, which is not greater than 9, so continue.
      • Push 9 onto the stack: st = [10, 9].
    • i = 2 (nums[i] = 8):

      • Stack contains 9, which is greater than 8.
      • Check second for an element greater than 8:
        • second.upper_bound(8) finds 9, which is greater than 8.
        • A 132 pattern is found with 8 < 9 and 9 < 10.
      • Return True.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

  • Time Complexity: The time complexity is due to the use of the SortedSet to find the higher bound, which takes time for each insertion and query. The overall complexity is since we iterate through the list once and perform log-time operations on the set.
  • Space Complexity: The space complexity is for the stack and set, which can store up to (n) elements in the worst case.

Solution Using Stack

To solve this problem, we need to find a sequence of numbers in the array that follows the pattern 132. Specifically, we need to find indices i, j, and k such that i < j < k and nums[i] < nums[k] < nums[j].

We can achieve this by iterating backward through the array, using a stack to keep track of potential values for nums[k]. By maintaining a variable z to represent the largest value we have found that is smaller than the current number, we can efficiently check for the 132 pattern.

Step-by-Step Algorithm

  1. Initialization:

    • Initialize z to Integer.MIN_VALUE to represent the largest value smaller than the current number.
    • Create an empty stack to keep track of potential values for nums[k].
  2. Iterate Backward:

    • Loop through the array nums from the end to the beginning.
  3. Check for Pattern:

    • For each nums[i], check if it is less than z. If true, return True since we have found a 132 pattern.
  4. Update z and Stack:

    • While the stack is not empty and the top of the stack is less than nums[i], update z to the top value of the stack and pop the stack.
    • Push the current nums[i] onto the stack.
  5. Return Result:

    • If the loop completes without finding the pattern, return False.

Algorithm Walkthrough

Using the input: [9, 11, 8, 9, 10, 7, 9]

  1. Initialization:

    • z = Integer.MIN_VALUE
    • stack = []
  2. Iterate Backward:

    • Start from the last element and move to the first.
  3. Iteration Details:

    • Step 1: nums[6] = 9
      • Stack is empty, push 9 onto the stack.
      • stack = [9]
    • Step 2: nums[5] = 7
      • 7 is not less than z (which is Integer.MIN_VALUE).
      • Push 7 onto the stack.
      • stack = [9, 7]
    • Step 3: nums[4] = 10
      • 10 is not less than z.
      • While stack top is less than 10, update z and pop from the stack.
        • z = 7, stack = [9]
        • z = 9, stack = []
      • Push 10 onto the stack.
      • stack = [10]
    • Step 4: nums[3] = 9
      • 9 is not less than z (which is 9).
      • While stack top is less than 9, update z and pop from the stack.
        • z = 9, stack = [10]
      • Push 9 onto the stack.
      • stack = [10, 9]
    • Step 5: nums[2] = 8
      • 8 is less than z(9). So, return true. .

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

  • Building the stack: Each element is pushed onto the stack exactly once and can be popped from the stack at most once. Therefore, the operations of pushing and popping elements are each.
  • Overall: Since we iterate through the array exactly once and perform operations for each element (push and pop from the stack), the total time complexity is , where n is the number of elements in the array.

Space Complexity

  • Stack Space: In the worst case, all elements are pushed onto the stack, leading to a stack space usage of .
  • Variable Space: The additional space used by the variable z is .
  • Overall: The overall space complexity is , due to the space used by the stack.
132 Pattern (medium)
Valid Sudoku (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Solution Using Stack

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity